typedef pair<int, int> Jie;

Jie exGCD(int a, int b) {
	if (a == 1 && b == 0) {
		return Jie(1, 0);
	}
	int k = a / b, c = a % b;
	Jie xin = exGcd(b, c);
	return Jie(xin.second, xin.first - k * xin.second);
}

